package com.zhugang.week13.sort;

/**
 * @program algorithms
 * @description: findKthLargest
 * @author: chanzhugang
 * @create: 2022/10/19 00:23
 */
public class FindKthLargest {

    /**
     * 215 数组中的第K个最大元素
     * https://leetcode.cn/problems/kth-largest-element-in-an-array/
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        // 快排找分区点
        return quickSort(nums, 0, nums.length - 1, k);
    }

    private int quickSort(int[] nums, int p, int r, int k) {
        if (p > r) {
            return -1;
        }

        int q = partiton(nums, p, r);
        if (q - p + 1 == k) {
            return nums[q];
        } else if (q - p + 1 < k) {
            // 在右侧
            return quickSort(nums, q + 1, r, k - (q - p + 1));
        } else {
            // 在左侧
            return quickSort(nums, p, q - 1, k);
        }
    }

    private int partiton(int[] nums, int p, int r) {
        // 从大到小排序，求分区点下标
        int i = p - 1;
        int j = p;
        while (j < r) {
            if (nums[j] > nums[r]) {
                // j大，换到前面z
                swap(nums, i + 1, j);
                i++;
            }
            j++;
        }
        swap(nums, i + 1, r);
        return i + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}